import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
import java.util.PriorityQueue;

public class NewSuurballe {
	
	/**
	 * @author Dennis Meyer, Janis Ebert, Sebastian Brodehl
	 */
	
	static BufferedReader reader;
	static BufferedReader readerOut;
	private HashMap<Integer,Vertex> graph = null;
	private List<Edge> originalEdges = null;
	
	public static void main(String[] args) throws Exception {
		reader = new BufferedReader(new FileReader("suurballe_in.txt"));
		readerOut = new BufferedReader(new FileReader("suurballe_out.txt"));
		new NewSuurballe().run();
	}

	private void run() throws Exception {
		String line = reader.readLine();
		if(line == null) {reader.close(); return;}
		String[] split = line.split(" ");
		int Nof_vertices = Integer.parseInt(split[0]);
		int Nof_edges = Integer.parseInt(split[1]);
		graph = new HashMap<Integer,Vertex>();
		originalEdges = new ArrayList<Edge>();
		
		ArrayList<Edge> sEdges = new ArrayList<Edge>();
		graph.put(1, new Vertex(1, "1", 1));
	    graph.put(Nof_vertices, new Vertex(Nof_vertices, String.valueOf(Nof_vertices), Nof_vertices));
		for(int i = 2; i < Nof_vertices; i++){
			// Den Knoten splitten
			graph.put(Nof_vertices + i - 1, new Vertex(Nof_vertices + i - 1, i + "b", i));
			
			Vertex temp = new Vertex(i, String.valueOf(i), i);
			temp.adjacencies = new ArrayList<Edge>();
			temp.adjacencies.add(new Edge(temp, graph.get(Nof_vertices + i - 1), 0));
			graph.put(i, temp);
		}
		for(int i = 0; i< Nof_edges; i++){
			line = reader.readLine();
			split = line.split(" ");
			int[] intsplit = new int[split.length]; 
			
			for(int j=0; j< split.length;j++)
				intsplit[j] = Integer.parseInt(split[j]);
			
			Vertex source = graph.get(intsplit[0] == 1 ? 1 : intsplit[0] == Nof_vertices ? Nof_vertices : Nof_vertices + intsplit[0] - 1);
			Vertex destination = graph.get(intsplit[1]);
			Edge edge = new Edge(source, destination, intsplit[2]);
			if(source.adjacencies == null)
				source.adjacencies = new ArrayList<Edge>();
			
			source.adjacencies.add(edge);
			this.originalEdges.add(new Edge(graph.get(intsplit[0]), destination, intsplit[2]));
			//graph.put(intsplit[0] == 1 ? 1 : Nof_vertices + intsplit[0] - 2, source);
			
			if(destination.equals(graph.get(1)))
				sEdges.add(edge);
		}
		new NewSuurballe().Dijkstra(graph);
		
		// Neugewichtung
		for(Entry<Integer, Vertex> entry: graph.entrySet()){
			if(entry.getValue().adjacencies == null) continue;
			for(Edge edge: entry.getValue().adjacencies){
				Vertex u = edge.source;
				Vertex v = edge.destination;
				int cost = edge.weight;
				int newCost = cost - v.minDistance + u.minDistance;
				edge.reWeight = edge.weight;
				edge.weight = newCost;
			}
		}
		
		if(!sEdges.isEmpty()){
			for(Edge edge: sEdges){
				int tmp = edge.source.adjacencies.indexOf(edge);
				edge.source.adjacencies.remove(tmp);
			}
		}
		
		//erster pfad sichern
		List<Vertex> firstPath = new ArrayList<Vertex>();
        for (Vertex vertex = graph.get(Nof_vertices); vertex != null; vertex = vertex.previous) {
        	if (!firstPath.contains(this.graph.get(vertex.normalid)))
        		firstPath.add(0, this.graph.get(vertex.normalid));
        	if(vertex.previous != null){
        		Edge reverseEdge = new Edge(vertex, vertex.previous, 0);
        		if(vertex.adjacencies == null)
        			vertex.adjacencies = new ArrayList<Edge>();
        		vertex.adjacencies.add(reverseEdge);
        		
        		int tmp = vertex.previous.adjacencies.indexOf(new Edge(vertex.previous, vertex, 0));
        		vertex.previous.adjacencies.remove(tmp);
        	}
        }
        new NewSuurballe().Dijkstra(graph);
        
        //zweiten pfad sichern
        List<Vertex> secondPath = new ArrayList<Vertex>();
        for (Vertex vertex = graph.get(Nof_vertices); vertex != null; vertex = vertex.previous)
        	if (secondPath.isEmpty() || secondPath.get(0).normalid != vertex.normalid)
        		secondPath.add(0, this.graph.get(vertex.normalid));
        
        // Pfade zusammenbaun
        this.getTwoFinalPathes(firstPath, secondPath, graph.get(Nof_vertices));
        
        new NewSuurballe().run();
	}

	private void Dijkstra(HashMap<Integer,Vertex> graph) throws Exception {
		for(int i = 1; i<= graph.size(); i++){
			graph.get(i).minDistance = Integer.MAX_VALUE;
			graph.get(i).previous = null;
		}
		graph.get(1).minDistance = 0;
		PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
		vertexQueue.add(graph.get(1));
		while (!vertexQueue.isEmpty()) {
			Vertex head = vertexQueue.poll();
			if(head.adjacencies == null) continue;
			for (Edge edge : head.adjacencies) {
				Vertex v = edge.destination;
                int weight = edge.weight;
                int distanceThroughHead = head.minDistance + weight;
                if (distanceThroughHead < v.minDistance) {
                	vertexQueue.remove(v);
                	v.minDistance = distanceThroughHead ;
                	v.previous = head;
                	vertexQueue.add(v);
                }
			}
		}		
	}

	private void getTwoFinalPathes(List<Vertex> firstPath, List<Vertex> secondPath, Vertex endPoint) throws Exception{
	    List<Vertex> finalFirstPath = finalPathHelper(firstPath, secondPath, endPoint, true);
	    List<Vertex> finalSecondPath = finalPathHelper(firstPath, secondPath, endPoint, false);
	    printFinalEdgeWeight(finalFirstPath, finalSecondPath);
	}

	private List<Vertex> finalPathHelper(List<Vertex> firstPath,
			List<Vertex> secondPath, Vertex endPoint, boolean first) {
		int position = 1;
		List<Vertex> finalPath = new ArrayList<Vertex>();
		List<Vertex> tempVertexList = first ? firstPath : secondPath;
		List<Vertex> tempOtherVertexList = !first ? firstPath : secondPath;
		finalPath.add(tempVertexList.get(0));
		
		do{
			 Vertex vertexFirstPath = tempVertexList.get(position);
			 finalPath.add(vertexFirstPath);
			 
			 // Kommt der Knoten zweimal in dem Pfad vor, kann direkt zu dem letzten vorkommen dieses Kontens gesprungen werden.
             if (tempVertexList.lastIndexOf(vertexFirstPath) != tempVertexList.indexOf(vertexFirstPath)){ 
            	 position = tempVertexList.lastIndexOf(vertexFirstPath) + 1;
            	 continue;
             }
             if (tempOtherVertexList.contains(vertexFirstPath)){
                 // Überschneidung
                 position =  tempOtherVertexList.indexOf(vertexFirstPath) + 1;
                 
                 // Switchen der Listen
                 List<Vertex> temp = new ArrayList<Vertex>(tempOtherVertexList);
                 tempOtherVertexList = tempVertexList;
                 tempVertexList = temp;
             }
             else
                 position++;
		}
		while (!finalPath.contains(endPoint));
		
		return finalPath;
	}
	
	private void printFinalEdgeWeight(List<Vertex> finalFirstPath, List<Vertex> finalSecondPath) throws Exception
	{
		int weightFirstPath = 0, weightSecondPath = 0;
		for (int i = 0; i < finalFirstPath.size() - 1; i++)
		{
			Edge tempEdge = new Edge(finalFirstPath.get(i), finalFirstPath.get(i + 1), 0);
			weightFirstPath +=  this.originalEdges.get(this.originalEdges.indexOf(tempEdge)).weight;
		}
		for (int i = 0; i < finalSecondPath.size() - 1; i++)
		{
			Edge tempEdge = new Edge(finalSecondPath.get(i), finalSecondPath.get(i + 1), 0);
			weightSecondPath +=  this.originalEdges.get(this.originalEdges.indexOf(tempEdge)).weight;
		}
		
		int value = weightFirstPath + weightSecondPath;
	
		String line = readerOut.readLine();
		if(line == null) {readerOut.close(); return;}
		int rigthValue = Integer.parseInt(line);
		
		if(value != rigthValue){
			System.out.println("Error - wrong Answer.");
		} else {
			System.out.println(value);
		}
	}
}

class Vertex implements Comparable<Vertex> {
	public final int id;
	public final int normalid;
    public ArrayList<Edge> adjacencies;
    public int minDistance = Integer.MAX_VALUE;
    public String name;
    public Vertex previous;
    public Vertex(int newId, int normalid) { id = newId; this.normalid = normalid;}
    public Vertex(int newId, String name, int normalid) {
		id = newId; this.name = name; this.normalid = normalid;
	}
    public String toString() { return name ; }
	@Override
	public int compareTo(Vertex other)
	{ 
		return minDistance < other.minDistance ? -1 : minDistance > other.minDistance ? 1 : 0;
	}
	@Override
    public boolean equals(Object obj){
		if(obj instanceof Vertex){
			Vertex other = (Vertex) obj;
			if(this.id == other.id)
    			return true;
		}
		return false;
	}
}

class Edge {
    public final Vertex destination;
    public final Vertex source;
    public int weight;
    public int reWeight;
    public Edge(Vertex newSource, Vertex newDestination, int newWeight){ 
    	source = newSource;
    	destination = newDestination; 
    	weight = newWeight;
    }
    @Override
    public boolean equals(Object obj){
    	if(obj instanceof Edge){
    		Edge other = (Edge) obj;
    		if(this.source.equals(other.source) && this.destination.equals(other.destination))
    			return true;
    	}
		return false;
    }
    @Override
    public String toString() { return destination + " " + weight;}
}